Metode numerice - Aplicatii

Lucrarea 10.   Rezolvarea sistemelor de ecuatii neliniare: metoda Newton si metode de gradient

Tema A - Metoda Newton               <----------- algoritm

Tema B - Metode de descrestere


   Modelul general al unui sistem de ecuatii neliniare de ordin n are forma:

unde f1, f2, ... , fn sunt functii neliniare ce depind de variabilele x1, x2, ... , xn care, la randul lor, reprezinta necunoscutele problemei. Cele n functii si n variabile pot fi privite ca doi vectori:
astfel incat sistemul poate fi scris compact, sub forma:
   Se considera ca sistemul de ecuatii neliniare admite solutia exacta x* = [x*1, x*2, ... , x*n]T, iar in vecinatatea lui x*, toate functiile fi si derivatele lor partiale sunt continue.    Toate metodele practice de rezolvare a sistemului de ecuatii neliniare sunt metode de tip iterativ. Exista si o serie de metode directe, dar acestea sunt mult prea specifice, referindu-se la forme cu totul si cu totul particulare ale sistemului. In principiu, exista trei mari categorii de metode iterative de rezolvare a sistemelor de ecuatii neliniare:
  1. metode bazate pe exprimarea explicita echivalenta a ecuatiilor sistemului, denumite pe scurt, chiar daca impropriu, metode de aproximatii succesive;
  2. metode care folosesc derivatele partiale ale functiilor fi, denumite metode de tip Newton;
  3. metode de minimizare, numite si metode de descrestere sau metode de gradient;
   Primele doua categorii de metode sunt principial asemanatoare cu metodele omonime destinate rezolvarii ecuatiilor neliniare. O asemenea constatare nu trebuie sa surprinda, deoarece o ecuatie este un caz particular al unui sistem de ecuatii.

Tema A - Metoda Newton

   Pentru sistemul de ecuatii neliniare :
metoda Newton apeleaza la o serie de aproximari care conduc la liniarizarea problemei. In cele din urma, problema se reduce la rezolvarea unui sir de sisteme de ecuatii liniare, pentru care se poate aplica oricare din metodele cunoscute.    Admitem ca la iteratia k s-a determinat o aproximatie xk = [x1k, x2k, ... , xnk]T, care se abate de la solutia exacta x* cu vectorul dxk = [dx1k, dx2k, ... , dxnk]T :
In ipoteza in care abaterile dxik (i=1,...,n) sunt suficient de mici, functiile fi(x*) pot fi dezvoltate in serii Taylor in jurul punctului xk, retinand numai termenii de ordinul intai:
Aceasta expresie poate fi scrisa compact, sub forma matriceala:
unde matricea J, formata din derivatele partiale ale functiilor ce definesc sistemul neliniar, este matricea Jacobian:
   Deoarece x* reprezinta solutia exacta a problemei, se anuleaza, astfel incat:
care reprezinta un sistem de ecuatii liniare ce are ca necunoscute corectiile dxk = [dx1k, dx2k, ... , dxnk]T. Dupa rezolvarea acestui sistem si inlocuirea lui dxk se poate determina solutia x*. Datorita insa neglijarilor facute la dezvoltarea in serii Taylor, corectiile calculate dxk nu mai asigura deplasarea completa din aproximatia xk pana la solutia exacta x*, ci pana la o noua aproximatie a acesteia:
Ultimele doua expresii reprezinta relatiile de recurenta pe baza carora se desfasoara procesul iterativ al metodei Newton, pornind de la o aproximatie x0.    Conditiile de convergenta ale metodei Newton au o formulare relativ complexa, iar in practica verificarea lor este, daca nu imposibila, atunci extrem de costisitoare ca timp de calcul. De aceea, controlul convergentei / divergentei se face ca si in cazul celorlalte metode iterative, prin impunerea unui numar maxim de iteratii.

Algoritmul 1 - Rezolvarea sistemelor de ecuatii neliniare cu metotda Newton
  1. Definirea sistemului de ecuatii neliniare: ordinul n , functiile fi(x) si derivatele partiale (i=1,...,n);
  2. Definirea parametrilor de iterare: abaterea maxima admisa a aproximatiilor in doua iteratii succesive Ex, abaterea maxima admisa a functiilor fi fata de zero Ef si numarul maxim de iteratii Nmax;
  3. Definirea aproximatiei initiale xi (i=1,...,n) si calculul valorilor functiei fi(x) (i=1,...,n);
  4. Procesul iterativ:
    1. Initializarea procesului iterativ: It <-- 0;
    2. Initializarea criteriului de oprire: Stop <-- false;
    3. Daca s-a atins numarul maxim de iteratii (It=Nmax) sau s-a atins criteriul de oprire (Stop=true), se intrerupe procesul iterativ si se trece la pasul 5;
    4. Trecerea la o noua iteratie: It <-- It+1;
    5. Memorarea aproximatiei din iteratia anterioara: zi <-- xi (i=1,...,n);
    6. Calculul matricei Jacobian J pentru aproximatia curenta:
    7. Rezolvarea sistemului de ecuatii liniare:
    8. Calculul noii aproximatii:
    9. Calculul valorilor functiilor pentru noua aproximatie: fi(x) (i=1,...,n);
    10. Calculul abaterilor:
    11. Stabilirea valorii criteriului de oprire:
    12. Se revine la pasul 4.3;
  5. Stabilirea conditiilor de iesire din bucla iterativa:
    • daca Stop=true, se afiseaza solutia aproximativa xi (i=1,...,n);
    • daca Stop= false, se afiseaza mesajul "Depasire numar maxim iteratii".


Tema B - Metode de descrestere

   Metodele de descrestere reprezinta cai indirecte de rezolvare a sistemelor de ecuatii neliniare, care transforma sistemul :
intr-o problema de optimizare neliniara fara restrictii. Sistemului de ecuatii i se asociaza o functie definita in raport cu toate cele n necunoscute F(x) = F(x1, x2, ... , xn), care se bucura de proprietatea de a prezenta un punct de extrem (cel mai frecvent un minim) in solutia exacta a sistemului de ecuatii x*=[x*1, x*2, ... , x*n]T. Astfel, prin aplicarea unei metode de optimizare functiei F(x), in sensul extremizarii valorii sale, se determina simultan si solutia aproximativa a sistemului originar. O asemenea functie F(x) se defineste ca produsul scalar al functiei asociate sistemului originar cu ea insasi :
Se verifica simplu ca solutia sistemului de ecuatii reprezinta punctul de minim global al functiei F(x).
   Dintre metodele de descrestere folosite mai frecvent se remarca metoda gradientului si metoda gradientului conjugat. Ambele metode minimizeaza functia F(x) prin deplasarea de la o aproximatie la alta in lungul unei directii care depinde de gradientul . O caracteristica remarcabila a acestor metode o reprezinta forma particulara a expresiei gradientului functiei F(x):
unde J(x) este matricea Jacobian atasata sistemului originar.

      Metoda gradientului

   Metoda gradientului porneste de la o aproximatie initiala x0 pe care cauta sa o imbunatateasca prin aplicarea unor corectii succesive orientate dupa directia gradientului functiei de optimizat si proportionale cu acesta. Deoarece vectorul gradient este orientat intotdeauna in sensul cresterii valorii functiei F(x), pentru minimizarea acestei functii corectiile se vor aplica intotdeauna in sens opus gradientului:
In relatia de mai sus dk reprezinta directia de deplasare la iteratia k, iar k este un coeficient care descrie amploarea deplasarii in directia dk. Coeficientul k se alege la fiecare iteratie astfel incat deplasarea in directia dk sa conduca la descresterea maxima a functiei F(x).    Pentru determinarea valorii optime a coeficientului k, functia F(x) calculata in noua aproximatie xk+1 se exprima ca o functie de k:
sau:
Daca se admite ca factorul k are valori suficient de mici, pentru a putea neglija puterile sale superioare lui 1, functiile fi pot fi dezvoltate in serii Taylor in jurul punctului xk, neglijand toti termenii neliniari:
sau:
   Functia F(xk+1) va atinge valoarea minima in acel punct xk+1 pentru care are loc anularea derivatei functiei g in raport cu k :
Solutia acestei ecuatii este :
Aceasta relatie mai poate fi scrisa sub forma condensata:
unde parantezele unghiulare indica produsul scalar a doi vectori. Pe baza relatiilor de mai sus se poate defini urmatoarea schema de aplicare a metodei gradientului:

Schema de aplicare a metodei gradientului

In aceste relatii expresia coeficientului k este diferita, dar echivalenta cu cea stabilita anterior. La numitor, gradientul gk a fost inlocuit cu directia de deplasare dk, pentru a permite efectuarea unei comparatii intre metoda gradientului si metoda gradientului conjugat ce va fi prezentata mai jos.    Se constata ca, in comparatie cu metodele de tip Newton, metoda gradientului nu necesita inversarea matricei Jacobian si nici rezolvarea unui sistem de ecuatii liniare, insa presupune efectuarea unui numar sporit de inmultiri matriceale, legate de stabilirea valorii optime a coeficientului k.

      Metoda gradientului conjugat

   Algoritmul acestei metode este foarte asemanator cu cel prezentat pentru metoda gradientului simplu. De aceasta data, insa, la o iteratie k, directia de deplasare dk se determina ca o combinatie liniara dintre gradientul gk luat cu semn schimbat si directia de deplasare din iteratia anterioara:
unde coeficientul k are expresia:
In aceste conditii, schema de aplicare a metodei gradientului conjugat este urmatoarea:

Schema de aplicare a metodei gradientului conjugat

   Se constata ca pentru prima iteratie nu se poate calcula un coeficient k, astfel incat pornirea algoritmului se face conform metodei gradientului, pentru care se alege d0 = - g0.

Pentru detalii suplimenatare privind rezolvarea sistemelor de ecuatii neliniare, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".
 

   Aplicatii - Lista lucrarilor de laborator